/*
 * @lc app=leetcode.cn id=213 lang=cpp
 *
 * [213] 打家劫舍 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0], nums[1]);

        vector<int> dp(nums.size() + 10, 0);

        dp[2] = nums[1];//不能偷窃nums[0]，那么能偷的就是 1...n-1
        for(int i = 3; i < nums.size() + 1; i++)
        {
            dp[i] = max(dp[i-2] + nums[i-1], dp[i-1]);
        }

        //不能偷窃nums[n-1]，那么能偷的就是0...n-2
        int ans = dp[nums.size()];
        dp[1] = nums[0];
        for(int i = 2; i < nums.size(); i++)
        {
            dp[i] = max(dp[i-2] + nums[i-1], dp[i-1]);
        }
        return max(ans, dp[nums.size() - 1]);
    }
};

// int main()
// {
//     vector<int> v = {1,2,3,1};
//     Solution().rob(v);
//     return 0;
// }
// @lc code=end

